// Copyright 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "content/browser/dom_storage/session_storage_database.h"

#include <inttypes.h>
#include <stddef.h>

#include <vector>

#include "base/files/file_util.h"
#include "base/logging.h"
#include "base/metrics/histogram_macros.h"
#include "base/strings/string_number_conversions.h"
#include "base/strings/stringprintf.h"
#include "base/strings/utf_string_conversions.h"
#include "base/trace_event/memory_dump_manager.h"
#include "base/trace_event/process_memory_dump.h"
#include "third_party/leveldatabase/env_chromium.h"
#include "third_party/leveldatabase/src/include/leveldb/db.h"
#include "third_party/leveldatabase/src/include/leveldb/iterator.h"
#include "third_party/leveldatabase/src/include/leveldb/options.h"
#include "third_party/leveldatabase/src/include/leveldb/status.h"
#include "third_party/leveldatabase/src/include/leveldb/write_batch.h"
#include "url/gurl.h"

namespace {

const char session_storage_uma_name[] = "SessionStorageDatabase.Open";

enum SessionStorageUMA {
    SESSION_STORAGE_UMA_SUCCESS,
    SESSION_STORAGE_UMA_RECREATED,
    SESSION_STORAGE_UMA_RECREATE_FAIL, // Deprecated in M56 (issue 183679)
    SESSION_STORAGE_UMA_RECREATE_NOT_FOUND,
    SESSION_STORAGE_UMA_RECREATE_NOT_SUPPORTED,
    SESSION_STORAGE_UMA_RECREATE_CORRUPTION,
    SESSION_STORAGE_UMA_RECREATE_INVALID_ARGUMENT,
    SESSION_STORAGE_UMA_RECREATE_IO_ERROR,
    SESSION_STORAGE_UMA_MAX
};

} // namespace

// Layout of the database:
// | key                            | value                              |
// -----------------------------------------------------------------------
// | map-1-                         | 2 (refcount, start of map-1-* keys)|
// | map-1-a                        | b (a = b in map 1)                 |
// | ...                            |                                    |
// | namespace-                     | dummy (start of namespace-* keys)  |
// | namespace-1- (1 = namespace id)| dummy (start of namespace-1-* keys)|
// | namespace-1-origin1            | 1 (mapid)                          |
// | namespace-1-origin2            | 2                                  |
// | namespace-2-                   | dummy                              |
// | namespace-2-origin1            | 1 (shallow copy)                   |
// | namespace-2-origin2            | 2 (shallow copy)                   |
// | namespace-3-                   | dummy                              |
// | namespace-3-origin1            | 3 (deep copy)                      |
// | namespace-3-origin2            | 2 (shallow copy)                   |
// | next-map-id                    | 4                                  |

namespace content {

// This class keeps track of ongoing operations across different threads. When
// DB inconsistency is detected, we need to 1) make sure no new operations start
// 2) wait until all current operations finish, and let the last one of them
// close the DB and delete the data. The DB will remain empty for the rest of
// the run, and will be recreated during the next run. We cannot hope to recover
// during this run, since the upper layer will have a different idea about what
// should be in the database.
class SessionStorageDatabase::DBOperation {
public:
    explicit DBOperation(SessionStorageDatabase* session_storage_database)
        : session_storage_database_(session_storage_database)
    {
        base::AutoLock auto_lock(session_storage_database_->db_lock_);
        ++session_storage_database_->operation_count_;
    }

    ~DBOperation()
    {
        base::AutoLock auto_lock(session_storage_database_->db_lock_);
        --session_storage_database_->operation_count_;
        if ((session_storage_database_->is_inconsistent_ || session_storage_database_->db_error_) && session_storage_database_->operation_count_ == 0 && !session_storage_database_->invalid_db_deleted_) {
            // No other operations are ongoing and the data is bad -> delete it now.
            session_storage_database_->db_.reset();
            leveldb::DestroyDB(session_storage_database_->file_path_.AsUTF8Unsafe(),
                leveldb::Options());
            session_storage_database_->invalid_db_deleted_ = true;
        }
    }

private:
    SessionStorageDatabase* session_storage_database_;
};

SessionStorageDatabase::SessionStorageDatabase(const base::FilePath& file_path)
    : file_path_(file_path)
    , db_error_(false)
    , is_inconsistent_(false)
    , invalid_db_deleted_(false)
    , operation_count_(0)
{
}

SessionStorageDatabase::~SessionStorageDatabase()
{
}

void SessionStorageDatabase::ReadAreaValues(const std::string& namespace_id,
    const GURL& origin,
    DOMStorageValuesMap* result)
{
    // We don't create a database if it doesn't exist. In that case, there is
    // nothing to be added to the result.
    if (!LazyOpen(false))
        return;
    DBOperation operation(this);

    // While ReadAreaValues is in progress, another thread can call
    // CommitAreaChanges. CommitAreaChanges might update map ref count key while
    // this thread is iterating over the map ref count key. To protect the reading
    // operation, create a snapshot and read from it.
    leveldb::ReadOptions options;
    options.snapshot = db_->GetSnapshot();

    std::string map_id;
    bool exists;
    if (GetMapForArea(namespace_id, origin.spec(), options, &exists, &map_id) && exists)
        ReadMap(map_id, options, result, false);
    db_->ReleaseSnapshot(options.snapshot);
}

bool SessionStorageDatabase::CommitAreaChanges(
    const std::string& namespace_id,
    const GURL& origin,
    bool clear_all_first,
    const DOMStorageValuesMap& changes)
{
    // Even if |changes| is empty, we need to write the appropriate placeholders
    // in the database, so that it can be later shallow-copied successfully.
    if (!LazyOpen(true))
        return false;
    DBOperation operation(this);

    leveldb::WriteBatch batch;
    // Ensure that the keys "namespace-" "namespace-N" (see the schema above)
    // exist.
    const bool kOkIfExists = true;
    if (!CreateNamespace(namespace_id, kOkIfExists, &batch))
        return false;

    std::string map_id;
    bool exists;
    if (!GetMapForArea(namespace_id, origin.spec(), leveldb::ReadOptions(),
            &exists, &map_id))
        return false;
    if (exists) {
        int64_t ref_count;
        if (!GetMapRefCount(map_id, &ref_count))
            return false;
        if (ref_count > 1) {
            if (!DeepCopyArea(namespace_id, origin, !clear_all_first,
                    &map_id, &batch))
                return false;
        } else if (clear_all_first) {
            if (!ClearMap(map_id, &batch))
                return false;
        }
    } else {
        // Map doesn't exist, create it now if needed.
        if (!changes.empty()) {
            if (!CreateMapForArea(namespace_id, origin, &map_id, &batch))
                return false;
        }
    }

    WriteValuesToMap(map_id, changes, &batch);

    leveldb::Status s = db_->Write(leveldb::WriteOptions(), &batch);
    UMA_HISTOGRAM_ENUMERATION("SessionStorageDatabase.Commit",
        leveldb_env::GetLevelDBStatusUMAValue(s),
        leveldb_env::LEVELDB_STATUS_MAX);
    return DatabaseErrorCheck(s.ok());
}

bool SessionStorageDatabase::CloneNamespace(
    const std::string& namespace_id, const std::string& new_namespace_id)
{
    // Go through all origins in the namespace |namespace_id|, create placeholders
    // for them in |new_namespace_id|, and associate them with the existing maps.

    // Example, data before shallow copy:
    // | map-1-                         | 1 (refcount)        |
    // | map-1-a                        | b                   |
    // | namespace-1- (1 = namespace id)| dummy               |
    // | namespace-1-origin1            | 1 (mapid)           |

    // Example, data after shallow copy:
    // | map-1-                         | 2 (inc. refcount)   |
    // | map-1-a                        | b                   |
    // | namespace-1-(1 = namespace id) | dummy               |
    // | namespace-1-origin1            | 1 (mapid)           |
    // | namespace-2-                   | dummy               |
    // | namespace-2-origin1            | 1 (mapid) << references the same map

    if (!LazyOpen(true))
        return false;
    DBOperation operation(this);

    leveldb::WriteBatch batch;
    const bool kOkIfExists = false;
    if (!CreateNamespace(new_namespace_id, kOkIfExists, &batch))
        return false;

    std::map<std::string, std::string> areas;
    if (!GetAreasInNamespace(namespace_id, &areas))
        return false;

    for (std::map<std::string, std::string>::const_iterator it = areas.begin();
         it != areas.end(); ++it) {
        const std::string& origin = it->first;
        const std::string& map_id = it->second;
        if (!IncreaseMapRefCount(map_id, &batch))
            return false;
        AddAreaToNamespace(new_namespace_id, origin, map_id, &batch);
    }
    leveldb::Status s = db_->Write(leveldb::WriteOptions(), &batch);
    return DatabaseErrorCheck(s.ok());
}

bool SessionStorageDatabase::DeleteArea(const std::string& namespace_id,
    const GURL& origin)
{
    if (!LazyOpen(false)) {
        // No need to create the database if it doesn't exist.
        return true;
    }
    DBOperation operation(this);
    leveldb::WriteBatch batch;
    if (!DeleteAreaHelper(namespace_id, origin.spec(), &batch))
        return false;
    leveldb::Status s = db_->Write(leveldb::WriteOptions(), &batch);
    return DatabaseErrorCheck(s.ok());
}

bool SessionStorageDatabase::DeleteNamespace(const std::string& namespace_id)
{
    {
        // The caller should have called other methods to open the DB before this
        // function. Otherwise, DB stores nothing interesting related to the
        // specified namespace.
        // Do nothing if the DB is not open (or we know it has failed already),
        base::AutoLock auto_lock(db_lock_);
        if (!IsOpen() || db_error_ || is_inconsistent_)
            return false;
    }
    DBOperation operation(this);
    // Itereate through the areas in the namespace.
    leveldb::WriteBatch batch;
    std::map<std::string, std::string> areas;
    if (!GetAreasInNamespace(namespace_id, &areas))
        return false;
    for (std::map<std::string, std::string>::const_iterator it = areas.begin();
         it != areas.end(); ++it) {
        const std::string& origin = it->first;
        if (!DeleteAreaHelper(namespace_id, origin, &batch))
            return false;
    }
    batch.Delete(NamespaceStartKey(namespace_id));
    leveldb::Status s = db_->Write(leveldb::WriteOptions(), &batch);
    return DatabaseErrorCheck(s.ok());
}

bool SessionStorageDatabase::ReadNamespacesAndOrigins(
    std::map<std::string, std::vector<GURL>>* namespaces_and_origins)
{
    if (!LazyOpen(true))
        return false;
    DBOperation operation(this);

    // While ReadNamespacesAndOrigins is in progress, another thread can call
    // CommitAreaChanges. To protect the reading operation, create a snapshot and
    // read from it.
    leveldb::ReadOptions options;
    options.snapshot = db_->GetSnapshot();

    std::string namespace_prefix = NamespacePrefix();
    std::unique_ptr<leveldb::Iterator> it(db_->NewIterator(options));
    it->Seek(namespace_prefix);
    // If the key is not found, the status of the iterator won't be IsNotFound(),
    // but the iterator will be invalid.
    if (!it->Valid()) {
        db_->ReleaseSnapshot(options.snapshot);
        return true;
    }

    if (!DatabaseErrorCheck(it->status().ok())) {
        db_->ReleaseSnapshot(options.snapshot);
        return false;
    }

    // Skip the dummy entry "namespace-" and iterate the namespaces.
    std::string current_namespace_start_key;
    std::string current_namespace_id;
    for (it->Next(); it->Valid(); it->Next()) {
        std::string key = it->key().ToString();
        if (!base::StartsWith(key, namespace_prefix,
                base::CompareCase::SENSITIVE)) {
            // Iterated past the "namespace-" keys.
            break;
        }
        // For each namespace, the first key is "namespace-<namespaceid>-", and the
        // subsequent keys are "namespace-<namespaceid>-<origin>". Read the unique
        // "<namespaceid>" parts from the keys.
        if (current_namespace_start_key.empty() || key.substr(0, current_namespace_start_key.length()) != current_namespace_start_key) {
            // The key is of the form "namespace-<namespaceid>-" for a new
            // <namespaceid>.
            current_namespace_start_key = key;
            current_namespace_id = key.substr(namespace_prefix.length(),
                key.length() - namespace_prefix.length() - 1);
            // Ensure that we keep track of the namespace even if it doesn't contain
            // any origins.
            namespaces_and_origins->insert(
                std::make_pair(current_namespace_id, std::vector<GURL>()));
        } else {
            // The key is of the form "namespace-<namespaceid>-<origin>".
            std::string origin = key.substr(current_namespace_start_key.length());
            (*namespaces_and_origins)[current_namespace_id].push_back(GURL(origin));
        }
    }
    db_->ReleaseSnapshot(options.snapshot);
    return true;
}

void SessionStorageDatabase::OnMemoryDump(
    base::trace_event::ProcessMemoryDump* pmd)
{
    std::string db_memory_usage;
    {
        base::AutoLock lock(db_lock_);
        if (!db_)
            return;

        bool res = db_->GetProperty("leveldb.approximate-memory-usage", &db_memory_usage);
        DCHECK(res);
    }

    uint64_t size;
    bool res = base::StringToUint64(db_memory_usage, &size);
    DCHECK(res);

    auto* mad = pmd->CreateAllocatorDump(
        base::StringPrintf("dom_storage/session_storage_0x%" PRIXPTR,
            reinterpret_cast<uintptr_t>(this)));
    mad->AddScalar(base::trace_event::MemoryAllocatorDump::kNameSize,
        base::trace_event::MemoryAllocatorDump::kUnitsBytes, size);

    // Memory is allocated from system allocator (malloc).
    const char* system_allocator_name = base::trace_event::MemoryDumpManager::GetInstance()
                                            ->system_allocator_pool_name();
    if (system_allocator_name)
        pmd->AddSuballocation(mad->guid(), system_allocator_name);
}

bool SessionStorageDatabase::LazyOpen(bool create_if_needed)
{
    base::AutoLock auto_lock(db_lock_);
    if (db_error_ || is_inconsistent_) {
        // Don't try to open a database that we know has failed already.
        return false;
    }
    if (IsOpen())
        return true;

    if (!create_if_needed && (!base::PathExists(file_path_) || base::IsDirectoryEmpty(file_path_))) {
        // If the directory doesn't exist already and we haven't been asked to
        // create a file on disk, then we don't bother opening the database. This
        // means we wait until we absolutely need to put something onto disk before
        // we do so.
        return false;
    }

    leveldb::DB* db;
    leveldb::Status s = TryToOpen(&db);
    if (!s.ok()) {
        LOG(WARNING) << "Failed to open leveldb in " << file_path_.value()
                     << ", error: " << s.ToString();
        DCHECK(db == NULL);

        // Clear the directory and try again.
        base::DeleteFile(file_path_, true);
        s = TryToOpen(&db);
        if (!s.ok()) {
            LOG(WARNING) << "Failed to open leveldb in " << file_path_.value()
                         << ", error: " << s.ToString();
            if (s.IsNotFound()) {
                UMA_HISTOGRAM_ENUMERATION(session_storage_uma_name,
                    SESSION_STORAGE_UMA_RECREATE_NOT_FOUND,
                    SESSION_STORAGE_UMA_MAX);
            } else if (s.IsNotSupportedError()) {
                UMA_HISTOGRAM_ENUMERATION(session_storage_uma_name,
                    SESSION_STORAGE_UMA_RECREATE_NOT_SUPPORTED,
                    SESSION_STORAGE_UMA_MAX);
            } else if (s.IsCorruption()) {
                UMA_HISTOGRAM_ENUMERATION(session_storage_uma_name,
                    SESSION_STORAGE_UMA_RECREATE_CORRUPTION,
                    SESSION_STORAGE_UMA_MAX);
            } else if (s.IsInvalidArgument()) {
                UMA_HISTOGRAM_ENUMERATION(session_storage_uma_name,
                    SESSION_STORAGE_UMA_RECREATE_INVALID_ARGUMENT,
                    SESSION_STORAGE_UMA_MAX);
            } else if (s.IsIOError()) {
                UMA_HISTOGRAM_ENUMERATION(session_storage_uma_name,
                    SESSION_STORAGE_UMA_RECREATE_IO_ERROR,
                    SESSION_STORAGE_UMA_MAX);
            } else {
                NOTREACHED();
            }

            DCHECK(db == NULL);
            db_error_ = true;
            return false;
        }
        UMA_HISTOGRAM_ENUMERATION(session_storage_uma_name,
            SESSION_STORAGE_UMA_RECREATED,
            SESSION_STORAGE_UMA_MAX);
    } else {
        UMA_HISTOGRAM_ENUMERATION(session_storage_uma_name,
            SESSION_STORAGE_UMA_SUCCESS,
            SESSION_STORAGE_UMA_MAX);
    }
    db_.reset(db);
    return true;
}

leveldb::Status SessionStorageDatabase::TryToOpen(leveldb::DB** db)
{
    leveldb::Options options;
    // The directory exists but a valid leveldb database might not exist inside it
    // (e.g., a subset of the needed files might be missing). Handle this
    // situation gracefully by creating the database now.
    options.max_open_files = 0; // Use minimum.
    options.create_if_missing = true;
    options.reuse_logs = leveldb_env::kDefaultLogReuseOptionValue;
    // Default write_buffer_size is 4 MB but that might leave a 3.999
    // memory allocation in RAM from a log file recovery.
    options.write_buffer_size = 64 * 1024;
    return leveldb::DB::Open(options, file_path_.AsUTF8Unsafe(), db);
}

bool SessionStorageDatabase::IsOpen() const
{
    return db_.get() != NULL;
}

bool SessionStorageDatabase::CallerErrorCheck(bool ok) const
{
    DCHECK(ok);
    return ok;
}

bool SessionStorageDatabase::ConsistencyCheck(bool ok)
{
    if (ok)
        return true;
    base::AutoLock auto_lock(db_lock_);
    // We cannot recover the database during this run, e.g., the upper layer can
    // have a different understanding of the database state (shallow and deep
    // copies). Make further operations fail. The next operation that finishes
    // will delete the data, and next run will recerate the database.
    is_inconsistent_ = true;
    return false;
}

bool SessionStorageDatabase::DatabaseErrorCheck(bool ok)
{
    if (ok)
        return true;
    base::AutoLock auto_lock(db_lock_);
    // Make further operations fail. The next operation that finishes
    // will delete the data, and next run will recerate the database.
    db_error_ = true;
    return false;
}

bool SessionStorageDatabase::CreateNamespace(const std::string& namespace_id,
    bool ok_if_exists,
    leveldb::WriteBatch* batch)
{
    leveldb::Slice namespace_prefix = NamespacePrefix();
    std::string dummy;
    leveldb::Status s = db_->Get(leveldb::ReadOptions(), namespace_prefix,
        &dummy);
    if (!DatabaseErrorCheck(s.ok() || s.IsNotFound()))
        return false;
    if (s.IsNotFound())
        batch->Put(namespace_prefix, "");

    std::string namespace_start_key = NamespaceStartKey(namespace_id);
    s = db_->Get(leveldb::ReadOptions(), namespace_start_key, &dummy);
    if (!DatabaseErrorCheck(s.ok() || s.IsNotFound()))
        return false;
    if (s.IsNotFound()) {
        batch->Put(namespace_start_key, "");
        return true;
    }
    return CallerErrorCheck(ok_if_exists);
}

bool SessionStorageDatabase::GetAreasInNamespace(
    const std::string& namespace_id,
    std::map<std::string, std::string>* areas)
{
    std::string namespace_start_key = NamespaceStartKey(namespace_id);
    std::unique_ptr<leveldb::Iterator> it(
        db_->NewIterator(leveldb::ReadOptions()));
    it->Seek(namespace_start_key);
    // If the key is not found, the status of the iterator won't be IsNotFound(),
    // but the iterator will be invalid.
    if (!it->Valid()) {
        // The namespace_start_key is not found when the namespace doesn't contain
        // any areas. We don't need to do anything.
        return true;
    }
    if (!DatabaseErrorCheck(it->status().ok()))
        return false;

    // Skip the dummy entry "namespace-<namespaceid>-" and iterate the origins.
    for (it->Next(); it->Valid(); it->Next()) {
        std::string key = it->key().ToString();
        if (!base::StartsWith(key, namespace_start_key,
                base::CompareCase::SENSITIVE)) {
            // Iterated past the origins for this namespace.
            break;
        }
        std::string origin = key.substr(namespace_start_key.length());
        std::string map_id = it->value().ToString();
        (*areas)[origin] = map_id;
    }
    return true;
}

void SessionStorageDatabase::AddAreaToNamespace(const std::string& namespace_id,
    const std::string& origin,
    const std::string& map_id,
    leveldb::WriteBatch* batch)
{
    std::string namespace_key = NamespaceKey(namespace_id, origin);
    batch->Put(namespace_key, map_id);
}

bool SessionStorageDatabase::DeleteAreaHelper(
    const std::string& namespace_id,
    const std::string& origin,
    leveldb::WriteBatch* batch)
{
    std::string map_id;
    bool exists;
    if (!GetMapForArea(namespace_id, origin, leveldb::ReadOptions(), &exists,
            &map_id))
        return false;
    if (!exists)
        return true; // Nothing to delete.
    if (!DecreaseMapRefCount(map_id, 1, batch))
        return false;
    std::string namespace_key = NamespaceKey(namespace_id, origin);
    batch->Delete(namespace_key);

    // If this was the only area in the namespace, delete the namespace start key,
    // too.
    std::string namespace_start_key = NamespaceStartKey(namespace_id);
    std::unique_ptr<leveldb::Iterator> it(
        db_->NewIterator(leveldb::ReadOptions()));
    it->Seek(namespace_start_key);
    if (!ConsistencyCheck(it->Valid()))
        return false;
    // Advance the iterator 2 times (we still haven't really deleted
    // namespace_key).
    it->Next();
    if (!ConsistencyCheck(it->Valid()))
        return false;
    it->Next();
    if (!it->Valid())
        return true;
    std::string key = it->key().ToString();
    if (!base::StartsWith(key, namespace_start_key, base::CompareCase::SENSITIVE))
        batch->Delete(namespace_start_key);
    return true;
}

bool SessionStorageDatabase::GetMapForArea(const std::string& namespace_id,
    const std::string& origin,
    const leveldb::ReadOptions& options,
    bool* exists, std::string* map_id)
{
    std::string namespace_key = NamespaceKey(namespace_id, origin);
    leveldb::Status s = db_->Get(options, namespace_key, map_id);
    if (s.IsNotFound()) {
        *exists = false;
        return true;
    }
    *exists = true;
    return DatabaseErrorCheck(s.ok());
}

bool SessionStorageDatabase::CreateMapForArea(const std::string& namespace_id,
    const GURL& origin,
    std::string* map_id,
    leveldb::WriteBatch* batch)
{
    leveldb::Slice next_map_id_key = NextMapIdKey();
    leveldb::Status s = db_->Get(leveldb::ReadOptions(), next_map_id_key, map_id);
    if (!DatabaseErrorCheck(s.ok() || s.IsNotFound()))
        return false;
    int64_t next_map_id = 0;
    if (s.IsNotFound()) {
        *map_id = "0";
    } else {
        bool conversion_ok = base::StringToInt64(*map_id, &next_map_id);
        if (!ConsistencyCheck(conversion_ok))
            return false;
    }
    batch->Put(next_map_id_key, base::Int64ToString(++next_map_id));
    std::string namespace_key = NamespaceKey(namespace_id, origin.spec());
    batch->Put(namespace_key, *map_id);
    batch->Put(MapRefCountKey(*map_id), "1");
    return true;
}

bool SessionStorageDatabase::ReadMap(const std::string& map_id,
    const leveldb::ReadOptions& options,
    DOMStorageValuesMap* result,
    bool only_keys)
{
    std::unique_ptr<leveldb::Iterator> it(db_->NewIterator(options));
    std::string map_start_key = MapRefCountKey(map_id);
    it->Seek(map_start_key);
    // If the key is not found, the status of the iterator won't be IsNotFound(),
    // but the iterator will be invalid. The map needs to exist, otherwise we have
    // a stale map_id in the database.
    if (!ConsistencyCheck(it->Valid()))
        return false;
    if (!DatabaseErrorCheck(it->status().ok()))
        return false;
    // Skip the dummy entry "map-<mapid>-".
    for (it->Next(); it->Valid(); it->Next()) {
        std::string key = it->key().ToString();
        if (!base::StartsWith(key, map_start_key, base::CompareCase::SENSITIVE)) {
            // Iterated past the keys in this map.
            break;
        }
        // Key is of the form "map-<mapid>-<key>".
        base::string16 key16 = base::UTF8ToUTF16(key.substr(map_start_key.length()));
        if (only_keys) {
            (*result)[key16] = base::NullableString16();
        } else {
            // Convert the raw data stored in std::string (it->value()) to raw data
            // stored in base::string16.
            size_t len = it->value().size() / sizeof(base::char16);
            const base::char16* data_ptr = reinterpret_cast<const base::char16*>(it->value().data());
            (*result)[key16] = base::NullableString16(base::string16(data_ptr, len), false);
        }
    }
    return true;
}

void SessionStorageDatabase::WriteValuesToMap(const std::string& map_id,
    const DOMStorageValuesMap& values,
    leveldb::WriteBatch* batch)
{
    for (DOMStorageValuesMap::const_iterator it = values.begin();
         it != values.end();
         ++it) {
        base::NullableString16 value = it->second;
        std::string key = MapKey(map_id, base::UTF16ToUTF8(it->first));
        if (value.is_null()) {
            batch->Delete(key);
        } else {
            // Convert the raw data stored in base::string16 to raw data stored in
            // std::string.
            const char* data = reinterpret_cast<const char*>(value.string().data());
            size_t size = value.string().size() * 2;
            batch->Put(key, leveldb::Slice(data, size));
        }
    }
}

bool SessionStorageDatabase::GetMapRefCount(const std::string& map_id,
    int64_t* ref_count)
{
    std::string ref_count_string;
    leveldb::Status s = db_->Get(leveldb::ReadOptions(),
        MapRefCountKey(map_id), &ref_count_string);
    if (!ConsistencyCheck(s.ok()))
        return false;
    bool conversion_ok = base::StringToInt64(ref_count_string, ref_count);
    return ConsistencyCheck(conversion_ok);
}

bool SessionStorageDatabase::IncreaseMapRefCount(const std::string& map_id,
    leveldb::WriteBatch* batch)
{
    // Increase the ref count for the map.
    int64_t old_ref_count;
    if (!GetMapRefCount(map_id, &old_ref_count))
        return false;
    batch->Put(MapRefCountKey(map_id), base::Int64ToString(++old_ref_count));
    return true;
}

bool SessionStorageDatabase::DecreaseMapRefCount(const std::string& map_id,
    int decrease,
    leveldb::WriteBatch* batch)
{
    // Decrease the ref count for the map.
    int64_t ref_count;
    if (!GetMapRefCount(map_id, &ref_count))
        return false;
    if (!ConsistencyCheck(decrease <= ref_count))
        return false;
    ref_count -= decrease;
    if (ref_count > 0) {
        batch->Put(MapRefCountKey(map_id), base::Int64ToString(ref_count));
    } else {
        // Clear all keys in the map.
        if (!ClearMap(map_id, batch))
            return false;
        batch->Delete(MapRefCountKey(map_id));
    }
    return true;
}

bool SessionStorageDatabase::ClearMap(const std::string& map_id,
    leveldb::WriteBatch* batch)
{
    DOMStorageValuesMap values;
    if (!ReadMap(map_id, leveldb::ReadOptions(), &values, true))
        return false;
    for (DOMStorageValuesMap::const_iterator it = values.begin();
         it != values.end(); ++it)
        batch->Delete(MapKey(map_id, base::UTF16ToUTF8(it->first)));
    return true;
}

bool SessionStorageDatabase::DeepCopyArea(
    const std::string& namespace_id, const GURL& origin, bool copy_data,
    std::string* map_id, leveldb::WriteBatch* batch)
{
    // Example, data before deep copy:
    // | namespace-1- (1 = namespace id)| dummy               |
    // | namespace-1-origin1            | 1 (mapid)           |
    // | namespace-2-                   | dummy               |
    // | namespace-2-origin1            | 1 (mapid) << references the same map
    // | map-1-                         | 2 (refcount)        |
    // | map-1-a                        | b                   |

    // Example, data after deep copy copy:
    // | namespace-1-(1 = namespace id) | dummy               |
    // | namespace-1-origin1            | 1 (mapid)           |
    // | namespace-2-                   | dummy               |
    // | namespace-2-origin1            | 2 (mapid) << references the new map
    // | map-1-                         | 1 (dec. refcount)   |
    // | map-1-a                        | b                   |
    // | map-2-                         | 1 (refcount)        |
    // | map-2-a                        | b                   |

    // Read the values from the old map here. If we don't need to copy the data,
    // this can stay empty.
    DOMStorageValuesMap values;
    if (copy_data && !ReadMap(*map_id, leveldb::ReadOptions(), &values, false))
        return false;
    if (!DecreaseMapRefCount(*map_id, 1, batch))
        return false;
    // Create a new map (this will also break the association to the old map) and
    // write the old data into it. This will write the id of the created map into
    // |map_id|.
    if (!CreateMapForArea(namespace_id, origin, map_id, batch))
        return false;
    WriteValuesToMap(*map_id, values, batch);
    return true;
}

std::string SessionStorageDatabase::NamespaceStartKey(
    const std::string& namespace_id)
{
    return base::StringPrintf("namespace-%s-", namespace_id.c_str());
}

std::string SessionStorageDatabase::NamespaceKey(
    const std::string& namespace_id, const std::string& origin)
{
    return base::StringPrintf("namespace-%s-%s", namespace_id.c_str(),
        origin.c_str());
}

const char* SessionStorageDatabase::NamespacePrefix()
{
    return "namespace-";
}

std::string SessionStorageDatabase::MapRefCountKey(const std::string& map_id)
{
    return base::StringPrintf("map-%s-", map_id.c_str());
}

std::string SessionStorageDatabase::MapKey(const std::string& map_id,
    const std::string& key)
{
    return base::StringPrintf("map-%s-%s", map_id.c_str(), key.c_str());
}

const char* SessionStorageDatabase::NextMapIdKey()
{
    return "next-map-id";
}

} // namespace content
